#ifndef DEQUE_H_
#define DEQUE_H_

#include <crtdbg.h>

template <typename Type>
class Deque
{
public:
	Deque()
	{
		capacity_ = defaultCapacity_;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	explicit Deque(int capacity)
	{
		_ASSERT(capacity > 0);
		capacity_ = capacity;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	~Deque(){ delete[] array_; }

	void clone(Deque& destination) const
	{
		delete[] destination.array_;
		destination.capacity_ = capacity_;
		destination.array_ = new Type[capacity_];
		destination.front_ = front_;
		destination.count_ = count_;

		for(int i = 0; i < count_; i++)
		{
			int index = (i + front_) % capacity_;
			destination.array_[index] = array_[index];
		}
	}

	int getCount() const{ return count_; }
	bool isEmpty() const{ return (count_ == 0); }

	Type& get(int index) const
	{
		_ASSERT(index >= 0);
		_ASSERT(index < count_);
		return array_[(front_ + index) % capacity_];
	}

	Type& operator [](int index) const
	{
		_ASSERT(index >= 0);
		_ASSERT(index < count_);
		return array_[(front_ + index) % capacity_];
	}

	int getCapacity() const{ return capacity_; }

	int indexOf(const Type& searchValue) const
	{
		for(int i = 0; i < count_; i++)
		{
			if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
		}
		return -1;
	}

	int lastIndexOf(const Type& searchValue) const
	{
		for(int i = count_ - 1; i >= 0; i--)
		{
			if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
		}
		return -1;
	}

	void pushFront(const Type& value)
	{
		if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
		front_--;
		if(front_ < 0){ front_ += capacity_; }
		array_[front_] = value;
		count_++;
	}

	void pushBack(const Type& value)
	{
		if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
		array_[(front_ + count_) % capacity_] = value;
		count_++;
	}

	Type popFront()
	{
		_ASSERT(count_ > 0);
		int resultIndex = front_;
		front_ = (front_ + 1) % capacity_;
		count_--;
		return array_[resultIndex];
	}

	Type popBack()
	{
		_ASSERT(count_ > 0);
		int resultIndex = (front_ + count_ - 1) % capacity_;
		count_--;
		return array_[resultIndex];
	}

	void set(int index, const Type& value) const
	{
		_ASSERT(index >= 0);
		_ASSERT(index < count_);
		array_[(front_ + index) % capacity_] = value;
	}

	Type remove(int index)
	{
		_ASSERT(index >= 0);
		_ASSERT(index < count_);
		_ASSERT(count_ > 0);
		Type result = array_[(front_ + index) % capacity_];
		count_--;
		if(index < (count_ / 2))
		{

			for(int i = index - 1; i >= 0; i--)
			{
				int source = (front_ + i) % capacity_;
				int destination = (source + 1) % capacity_;
				array_[destination] = array_[source];
			}

			front_ = (front_ + 1) % capacity_;
		}
		else
		{
			for(int i = index; i < count_; i++)
			{
				int destination = (front_ + i) % capacity_;
				int source = (destination + 1) % capacity_;
				array_[destination] = array_[source];
			}
		}
		return result;
	}

	int removeByValue(const Type& removeValue)
	{
		int index = lastIndexOf(removeValue);
		if(index == -1){ return index; }
		remove(index);
		return index;
	}

	void clear(){ front_ = count_ = 0; }

	void clear(int capacity)
	{
		_ASSERT(capacity >= 0);
		if(capacity <= 0){ capacity = 1; }
		delete[] array_;
		capacity_ = capacity;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	void setCapacity(int newCapacity)
	{
		_ASSERT(newCapacity >= count_);
		resize(newCapacity);
	}

	void trim()
	{
		if(count_ == 0) { resize(1);} else{ resize(count_); }
	}

	void sort( int(*compare)(const Type*, const Type*) )
	{
		if((front_ + count_) > capacity_)
		{
			if(count_ != capacity_)
			{
				int destination = (front_ + count_) % capacity_;
				for(int i = front_; i < capacity_; i++, destination++)
				{
					array_[destination] = array_[i];
				}
			}
			front_ = 0;
		}
		qsort(array_ + front_, count_, sizeof(Type),
			(int(*)(const void*, const void*))compare);
	}


	Type* search(Type key, int(*compare)(const Type*, const Type*) )
	{
		return (Type*)bsearch(&key, array_ + front_, count_, sizeof(Type),
			(int(*)(const void*, const void*))compare);
	}

private:
	void resize(int newCapacity)
	{
		_ASSERT(newCapacity > 0);
		Type* newArray = new Type[newCapacity];

		for(int i = 0; i < count_; i++)
		{
			int index = i + front_;
			int source = index % capacity_;
			int destination = index % newCapacity;
			newArray[destination] = array_[source];
		}
		delete[] array_;
		array_ = newArray;
		capacity_ = newCapacity;
	}

	Deque(const Deque& copy);

	void operator =(const Deque& copy);

	Type* array_;
	int front_;
	int count_;
	int capacity_;
	static const int defaultCapacity_ = 16;

};

#endif
